
package automaton;

import java.util.Set;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.HashMap;

import util.Predicate;
import util.Utils;


/**
 * Autómata finito no determinístico.
 * Este autómata se puede construir con no-determinismo, pero se ejecuta de
 * forma determinística.
 * 
 * @param <T> tipo de las transiciones; null se interpreta como la transición "lambda"
 */
public class NondeterministicAutomaton<T> extends Automaton<NDStateSet<T>, T> {
	
	private final NDState<T> initialState;
	private final Set<NDState<T>> states;
	
	private final Map<NDState<T>, HashSet<NDState<T>>> closures;
	
	/**
	 * Constructor.
	 * @param initialState el estado inicial
	 */
	public NondeterministicAutomaton(NDState<T> initialState) {
		this.states = new HashSet<NDState<T>>();
		this.initialState = initialState;
		this.states.add(initialState);
		
		this.closures = new HashMap<NDState<T>, HashSet<NDState<T>>>();
	}
	
	public NDStateSet<T> start() {
		calculateClosures();
		
		return new NDStateSet<T>(getClosure(initialState));
	}
	
	public NDStateSet<T> next(NDStateSet<T> current, T label) {
		HashSet<NDState<T>> next = new HashSet<NDState<T>>();
			
		for(NDState<T> c : current.getStates()) {
			for(NDState<T> n : c.next(label)) {
				next.addAll(getClosure(n));
			}
		}
		
		return new NDStateSet<T>(next);
	}

	public void addState(NDState<T> state) {
		states.add(state);
	}
	
	private HashSet<NDState<T>> getClosure(NDState<T> state) {
		return closures.get(state);
	}
	
	private void calculateClosures() {
		closures.clear();
				
		for(NDState<T> s : states) {
			HashSet<NDState<T>> c = new HashSet<NDState<T>>();
			c.add(s);
			closures.put(s, c);
		}
		
		boolean changed = true;
		while(changed) {
			changed = false;
			
			for(NDState<T> s1 : states) {
				HashSet<NDState<T>> prevClosure = closures.get(s1);
				HashSet<NDState<T>> nextClosure = new HashSet<NDState<T>>();
				nextClosure.addAll(prevClosure);
				
				for(NDState<T> s2 : prevClosure) {
					nextClosure.addAll(s2.next(null));
				}
				if(nextClosure.size() > prevClosure.size()) {
					closures.put(s1, nextClosure);
					changed = true;
				}
			}
		}
	}
	
	public NDState<T> getInitialState() {
		return initialState;
	}
	
	public Set<NDState<T>> getFinalStates() {
		Set<NDState<T>> ret = new HashSet<NDState<T>>();
		for(NDState<T> state : states) {
			if(state.isAcceptor())
				ret.add(state);
		}
		return ret;
	}
	
	public Set<NDState<T>> getStates() {
		return states;
	}
	
	public String toString() {
		String ret = "";
		int i = 0;
		for(NDState<T> s1 : states) {
			
			NDState<Character> s1char = (NDState<Character>)s1; // TODO
			
			ret += i + ": " + s1char + (s1char == initialState ? "(init)" : "");
			ret += "\n\tTransiciones lambda: ";
				for(NDState<Character> s2 : s1char.next(null))
					ret += s2 + ",";
			
			ret += "\n\tTransiciones 'a': ";
			for(NDState<Character> s2 : s1char.next('a'))
				ret += s2 + ",";
			
			ret += "\n\tTransiciones 'b': ";
			for(NDState<Character> s2 : s1char.next('b'))
				ret += s2 + ",";
			
			i++;
			ret += "\n";
		}
		
		return ret;
	}
	
}
